Implementation and analysis of an adaptive multilevel Monte Carlo algorithm

Implementation and analysis of an adaptive multilevel Monte Carlo algorithm

Håkon Hoel, Erik von Schwerin, Raul Tempone, and Anders Szepessy,  "Implementation and analysis of an adaptive multilevel Monte Carlo algorithm" Monte Carlo Methods and Applications. Volume 20, Issue 1, Pages 1–41, ISSN (Online) 1569-3961, ISSN (Print) 0929-9629, DOI: 10.1515/mcma-2013-0014, November 2013
 
Håkon Hoel, Erik von Schwerin, Raul Tempone, and Anders Szepessy
Computational finance, Monte Carlo, multilevel, adaptivity, weak approximation, error control, Euler--Maruyama method, a posteriori error estimates, backward dual functions, adjoints
2013
We present an adaptive multilevel Monte Carlo (MLMC) method for weak approximations of solutions to Itˆo stochastic differential equations (SDE). The work [Oper. Res. 56 (2008), 607–617] proposed and analyzed an MLMC method based on a hierarchy of uniform time discretizations and control variates to reduce the computational effort required by a single level Euler–Maruyama Monte Carlo method from  form1.pngto form2.pngfor a mean square error of form3.png. Later, the work [Lect. Notes Comput. Sci. Eng. 82, Springer, Berlin, 2012, 217–234] presented an MLMC method using a hierarchy of adaptively refined, non uniform time discretizations, and, as such, it may be considered a generalization of the uniform time discretization MLMC method.
This work improves the adaptive MLMC algorithms presented in [Lect. Notes Comput. Sci. Eng. 82, Springer, Berlin, 2012, 217–234] and it also provides mathematical analysis of the improved algorithms. In particular, we show that under some assumptions our adaptive MLMC algorithms are asymptotically accurate and essentially have the correct complexity but with improved control of the complexity constant factor in the asymptotic analysis. Numerical tests include one case with singular drift and one with stopped diffusion, where the complexity of a uniform single level method is form4.png. For both these cases the results confirm the theory, exhibiting savings in the computational cost for achieving the accuracy  form5.pngfrom form6.pngfor the adaptive single level algorithm to essentially form7.pngfor the adaptive MLMC algorithm.
ISSN (Print) 0929-9629